﻿/*
题目: 完全背包问题

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

https://www.acwing.com/problem/content/3/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

int main() {
    int N, V;
    cin >> N >> V;

    vector<int> v(N), w(N);
    for (int i = 0; i < N; i++) {
        cin >> v[i] >> w[i];
    }

    vector<vector<int>> dp(N + 1, vector<int>(V + 1, 0));

    for (int i = 1; i <= N; i++) {
        // 每个物品都能选无限个
        for (int j = 0; j <= V; j++) {
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);         // A> 选择不选
            if (j >= v[i - 1]) {                            // B> 可以选择拿, 可以选择第一次拿，也可以选择多次拿
                dp[i][j] = max(dp[i][j], max(dp[i - 1][j - v[i - 1]] + w[i - 1], dp[i][j - v[i - 1]] + w[i - 1]));
            }
        }
    }

    cout << dp[N][V] << endl;
    return 0;
}
